package DataStructureAndAlgorithm.BaseAlgorithm.Mathematics.快速幂;
import java.util.Scanner;
public class AcWing_875 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            int p = in.nextInt();
            int res = qmi(a,b,p);
            System.out.println(res);
        }
    }
    //求解快速幂，本质即将指数k进行二进制化，然后对被一位进行求幂
    static int qmi(int a,int k,int p){
        int res = 1;
        while (k > 0){
            if ((k & 1) != 0)res = (int)((long)res * a % p);
            k = (k >> 1);
            a = (int)((long)a * a % p);
        }
        return res;
    }
}
/*
给定 n 组 ai,bi,pi，对于每组数据，求出 abiimodpi

的值。
输入格式

第一行包含整数 n

。

接下来 n
行，每行包含三个整数 ai,bi,pi

。
输出格式

对于每组数据，输出一个结果，表示 abiimodpi

的值。

每个结果占一行。
数据范围

1≤n≤100000
,
1≤ai,bi,pi≤2×109

输入样例：

2
3 2 5
4 3 9

输出样例：

4
1

 */